package com.leetcode.study;

import java.util.Objects;

/**
 * 递归 <br/>
 *
 * 1、确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
 * 2、确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对
 * 3、确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
 * 参考一：https://zhuanlan.zhihu.com/p/377210603
 */
public class RecursionTest {


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        public int getVal() {
            return val;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(3);

        root.setLeft(left);
        root.setRight(right);

        System.out.println(">>>>>>>>>>>> 前序遍历 >>>>>>>>>>> 1 2 3");
        preorderTraversal(root);
        System.out.println(">>>>>>>>>>>> 中序遍历 >>>>>>>>>>> 2 1 3");
        inorderTraversal(root);
        System.out.println(">>>>>>>>>>>> 后序遍历 >>>>>>>>>>> 2 3 1");
        postorderTraversal(root);

    }

    /**
     * 前序遍历：根节点 -> 左子树 -> 右子树
     * @param root
     */
    public static void preorderTraversal(TreeNode root) {
        if (Objects.isNull(root)) {
            return;
        }

        System.out.println(root.getVal());
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    /**
     * 中序遍历：左子树 -> 根节点 -> 右子树
     * @param root
     */
    public static void inorderTraversal(TreeNode root) {
        if (Objects.isNull(root)) {
            return;
        }

        inorderTraversal(root.left);
        System.out.println(root.getVal());
        inorderTraversal(root.right);
    }


    /**
     * 后序遍历：左子树 -> 右子树 -> 根节点
     * @param root
     */
    public static void postorderTraversal(TreeNode root) {
        if (Objects.isNull(root)) {
            return;
        }

        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.println(root.getVal());
    }

}
